{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Лекция 5. Шаблоны"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Какая идея стоит за шаблонами"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ранее мы познакомились с возможностью перегрузки функций. Давайте вспомним её на примере swap:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// поменять местами два int\n",
    "void my_swap(int& a, int& b)\n",
    "{\n",
    "    int tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;    \n",
    "}\n",
    "\n",
    "// поменять местами два short\n",
    "void my_swap(short& a, short& b)\n",
    "{\n",
    "    short tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "\n",
    "// поменять местами два float\n",
    "void my_swap(float& a, float& b)\n",
    "{\n",
    "    float tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "\n",
    "...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вечер начинает быть томным ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для решения проблем дублирования кода придуманы шаблоны:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// напишем шаблон - как должна выглядеть функция\n",
    "template<typename T>\n",
    "void my_swap(T& a, T& b)\n",
    "{\n",
    "    T tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Применение шаблона:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int a = 3, b = 5;\n",
    "\n",
    "// вызов my_swap(int&, int&), тип T указывается программистом явно\n",
    "my_swap<int>(a, b);\n",
    "\n",
    "// вызов my_swap(int&, int&), тип T выводится компилятором автоматически\n",
    "my_swap(a, b); \n",
    "\n",
    "\n",
    "float x = 3.f, y = 5.f;\n",
    "my_swap(x, y);\n",
    "my_swap<float>(x, y);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Важное свойство шаблонов по сравнению с перегрузкой функций:\n",
    "* шаблон компилируется только тогда, когда он вызывается\n",
    "* шаблон компилируется только для тех типов, для которых он вызывается.\n",
    "\n",
    "_и в каждом cpp-файле шаблон компилируется снова и снова_\n",
    "\n",
    "Показать пример на godbolt.org, позакомментировать функции, продемонстрировать разницу в выхлопе компилятора."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <string>\n",
    "\n",
    "template<typename T>\n",
    "void __attribute__ ((noinline)) myswap(T& a, T& b)\n",
    "{\n",
    "    T tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    int i1 = 3, i2 = 5;\n",
    "    myswap(i1, i2);\n",
    "\n",
    "    float f1 = 3.f, f2 = 5.f;\n",
    "    myswap(f1, f2);\n",
    "\n",
    "    double d1 = 3., d2 = 5.;\n",
    "    myswap(d1, d2);\n",
    "\n",
    "    std::string s1 = \"abc\", s2 = \"def\";\n",
    "    myswap(s1, s2);\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Особенности шаблонов по сравнению с перегруженными функциями:\n",
    "* компилируется только то, что инстанциируется в коде\n",
    "* компилируется столько раз, в скольки единицах трансляции инстанциируется:\n",
    "    * можно в одном cpp-файле 10 раз позвать myswap(int&, int&) - эта функция скомпилируется единожды\n",
    "    * можно в 10 cpp-файлах один раз позвать myswap(int&, int&) - эта функция скомпилируется 10 раз\n",
    "* накладные расходы во время компиляции на кодогенерацию при истанциации\n",
    "* позволяет компилятору агрессивнее оптимизировать. Раскомментировать `__attribute__((noinline))` из примера и показать какой код сгенерирует компилятор. Объяснить, почему.\n",
    "* позволяет нарушать ODR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Коротко:\n",
    "\n",
    "* (+) меньше кода\n",
    "* (+) быстрее\n",
    "* (-) дольше компилируется\n",
    "* (-) сложнее писать"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопросы__:\n",
    "* Где поместить шаблонную функцию, которую нужно использовать в разных cpp-файлах?\n",
    "* Где поместить её реализацию?\n",
    "* Может ли шаблонная функция содержать некомпилирующийся код?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Специализация"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Перегрузка функций позволяла сделать `myswap` у `std::string` более эффективно, без лишнего копирования памяти:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void myswap(int& a, int& b) { ... }\n",
    "void myswap(short& a, short& b) { ... }\n",
    "\n",
    "void myswap(std::string& a, std::string& b)\n",
    "{\n",
    "    a.swap(b);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Шаблоны тоже позволяют специализировать поведение функций, если наложить на шаблонный параметр ограничение, например:\n",
    "\n",
    "(закинуть этот код на godbolt, показать во что компилируется программа)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <string>\n",
    "\n",
    "template<typename T>\n",
    "void __attribute__ ((noinline)) myswap(T& a, T& b)\n",
    "{\n",
    "    T tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "\n",
    "template<>\n",
    "void __attribute__ ((noinline)) myswap<std::string>(std::string& a, std::string& b)\n",
    "{\n",
    "    a.swap(b);\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    int i1 = 3, i2 = 5;\n",
    "    myswap(i1, i2);\n",
    "\n",
    "    float f1 = 3.f, f2 = 5.f;\n",
    "    myswap(f1, f2);\n",
    "\n",
    "    double d1 = 3., d2 = 5.;\n",
    "    myswap(d1, d2);\n",
    "\n",
    "    std::string s1 = \"abc\", s2 = \"def\";\n",
    "    myswap(s1, s2);\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во-первых, шаблон может иметь несколько параметров, а во-вторых, параметры не обязаны быть типами. Они могут быть, например, целыми числами:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<int N, typename T>\n",
    "T add_value(T x)\n",
    "{\n",
    "    return x + N;\n",
    "}\n",
    "\n",
    "int a = add_value<5, int>(100);\n",
    "int a = add_value<5>(100);\n",
    "\n",
    "// 1. шаблон специализирован программистом частично, тип Т компилятор определит сам\n",
    "// 2. параметром шаблона выступает целое число.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: Какую информацию здесь компилятор использует, чтобы вывести тип `T`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Шаблонные классы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Аналогично функциям, классы тоже могут быть шаблонными:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример структуры:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// N-мерный вектор из курса линейной алгебры типа T\n",
    "template<typename T, int N>\n",
    "struct VectorN\n",
    "{\n",
    "    T data[N];\n",
    "};\n",
    "\n",
    "// в качестве примера запишем операции сложения и умножения для таких векторов\n",
    "\n",
    "template<typename T, int N>\n",
    "VectorN<T, N> operator +(const VectorN<T, N>& l, const VectorN<T, N>& r)\n",
    "{\n",
    "    VectorN<T, N> rv;\n",
    "    for (int i = 0; i < N; ++i)\n",
    "        rv.data[i] = l.data[i] + r.data[i];\n",
    "    return rv;    \n",
    "}\n",
    "\n",
    "template<typename T, int N>\n",
    "T operator * (const VectorN<T, N>& l, const VectorN<T, N>& r)\n",
    "{\n",
    "    T rv = 0;\n",
    "    for (int i = 0; i < N; ++i)\n",
    "        rv += l.data[i] * r.data[i];\n",
    "    return rv;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример шаблонного класса:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напишем свой собственный `optional`. Он будет не так хорош, как `std::optional`, потому что мы не знаем пока всех необходимых трюков С++, но для начала пойдёт."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Идея `optional` - класс-обёртка над значением, которое может отсутствовать.\n",
    "\n",
    "Для начала объявим шаблонный класс:\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class Optional {\n",
    "    ...\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Добавим в класс поля:\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class Optional {\n",
    "    \n",
    "private:\n",
    "    T value_;\n",
    "    bool has_value_;\n",
    "    \n",
    "    ...\n",
    "};\n",
    "```\n",
    "\n",
    "**Вопрос:** Мы выбрали способ хранения объекта как поле класса, потому что так проще для демонстрации. Какие у него недостатки? Как их обойти?\n",
    "\n",
    "<details>\n",
    "<summary>Ответ</summary>\n",
    "\n",
    "* Недостаток - объект существует даже когда он не нужен\n",
    "* Вариант обхода 1 - хранить объект в куче через new. Проблема: расходы на new/delete.\n",
    "* Вариант обхода 2 - кусок сырой памяти под объект + placement new и ручной вызов деструкторов (трюк в std::optional)\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Добавим конструкторы:\n",
    "    \n",
    "```c++\n",
    "template<typename T>\n",
    "class Optional {\n",
    "    ...\n",
    "        \n",
    "public:\n",
    "    Optional()\n",
    "        : has_value_(false)\n",
    "    {}\n",
    "        \n",
    "    Optional(const T& another_value)\n",
    "        : value_(another_value)\n",
    "        , has_value_(true)\n",
    "    {}   \n",
    "};\n",
    "\n",
    "//\n",
    "// usage:\n",
    "//\n",
    "Optional<std::string> maybe_string_1;\n",
    "Optional<std::string> maybe_string_2(\"hello world\");\n",
    "```\n",
    "\n",
    "**Вопрос:** Почему `const &` у `another_value` ?\n",
    "\n",
    "**Вопрос:** Что мы должны срочно добавить в класс?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Срочно добавим:\n",
    "\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class Optional {\n",
    "    ...\n",
    "\n",
    "public:\n",
    "    Optional(const Optional&) = default;\n",
    "    Optional(Optional&&) = default;\n",
    "    Optional& operator = (const Optional&) = default;\n",
    "    Optional& operator = (Optional&&) = default;\n",
    "    ~Optional() = default;\n",
    "};\n",
    "\n",
    "//\n",
    "// usage:\n",
    "//\n",
    "Optional<std::string> maybe_string_1(\"hello world\");\n",
    "Optional<std::string> maybe_string_2 = maybe_string_1;\n",
    "Optional<std::string> maybe_string_3 = std::move(maybe_string_1);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Добавим немного функционала:\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class Optional {\n",
    "    ...\n",
    "        \n",
    "public:\n",
    "    bool has_value() const { return has_value_; }\n",
    "    \n",
    "    T&       get_value()       { return value_; }\n",
    "    const T& get_value() const { return value_; }\n",
    "    \n",
    "    T*       get_ptr()       { return has_value_ ? &value_ : nullptr; }    \n",
    "    const T* get_ptr() const { return has_value_ ? &value_ : nullptr; }\n",
    "    \n",
    "    void reset() {\n",
    "        value_ = T();\n",
    "        has_value_ = false;\n",
    "    }\n",
    "\n",
    "    void reset(const T& another_value) {\n",
    "        value_ = another_value;\n",
    "        has_value_ = true;\n",
    "    }\n",
    "    \n",
    "    void emplace() {\n",
    "        value_ = T();\n",
    "        has_value_ = true;\n",
    "    }\n",
    "};\n",
    "\n",
    "//\n",
    "// usage:\n",
    "//\n",
    "Optional<std::string> maybe_string_1(\"hello world\");\n",
    "\n",
    "if (maybe_string_1.has_value())\n",
    "    std::cout << maybe_string_1.get_value() << std::endl;\n",
    "\n",
    "if (std::string* s = maybe_string_1.get_ptr())\n",
    "    std::cout << *s << std::endl;\n",
    "\n",
    "maybe_string_1.reset();\n",
    "\n",
    "maybe_string_1.emplace();\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Добавим операторы сравнения:\n",
    "    \n",
    "```c++\n",
    "template<typename T>\n",
    "class Optional { ... };\n",
    "\n",
    "template<typename T>\n",
    "bool operator == (const Optional<T>& lhs, const Optional<T>& rhs) {\n",
    "    if (!lhs.has_value())\n",
    "        return !rhs.has_value();\n",
    "    \n",
    "    if (!rhs.has_value())\n",
    "        return false;\n",
    "    \n",
    "    return lhs.get_value() == rhs.get_value();    \n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "bool operator != (const Optional<T>& lhs, const Optional<T>& rhs) {\n",
    "    return !(lhs == rhs);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "bool operator == (const Optional<T>& lhs, const T& rhs) {\n",
    "    return\n",
    "        lhs.has_value() &&\n",
    "        lhs.get_value() == rhs;\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "bool operator == (const T& lhs, const Optional<T>& rhs) {\n",
    "    return rhs == lhs;\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "bool operator != (const Optional<T>& lhs, const T& rhs) {\n",
    "    return !(lhs == rhs);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "bool operator != (const T& lhs, const Optional<T>& rhs) {\n",
    "    return !(lhs == rhs);\n",
    "}\n",
    "\n",
    "\n",
    "\n",
    "//\n",
    "// usage:\n",
    "//\n",
    "Optional<std::string> maybe_string_1(\"hello world\");\n",
    "Optional<std::string> maybe_string_2 = maybe_string_1;\n",
    "\n",
    "if (maybe_string_1 != maybe_string_2)\n",
    "    std::cout << \"unreachable!\" << std::endl;\n",
    "\n",
    "Optional<int> maybe_int;\n",
    "\n",
    "if (maybe_string_1 == maybe_int)  // compile-time error!\n",
    "    std::cout << \"unreachable!\" << std::endl;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос:** какая проблема в этом коде?\n",
    "\n",
    "```c++\n",
    "Optional<std::string> maybe_string(\"hello world\");\n",
    "\n",
    "if (maybe_string == \"C++ is designed for faster code\")\n",
    "    std::cout << \"Fast enough?\" << std::endl;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Решим эту проблему, добавим ещё один более хитрый оператор сравнения:\n",
    "    \n",
    "```c++\n",
    "\n",
    "template<typename T, typename U>\n",
    "bool operator == (const Optional<T>& lhs, const U& rhs) {\n",
    "    return\n",
    "        lhs.has_value() &&\n",
    "        lhs.get_value() == rhs;\n",
    "}\n",
    "\n",
    "template<typename T, typename U>\n",
    "bool operator == (const T& lhs, const Optional<U>& rhs) {\n",
    "    return rhs == lhs;\n",
    "}\n",
    "\n",
    "template<typename T, typename U>\n",
    "bool operator != (const Optional<T>& lhs, const U& rhs) {\n",
    "    return !(lhs == rhs);\n",
    "}\n",
    "\n",
    "template<typename T, typename U>\n",
    "bool operator != (const T& lhs, const Optional<U>& rhs) {\n",
    "    return !(rhs == lhs);\n",
    "}\n",
    "\n",
    "//\n",
    "// usage:\n",
    "//\n",
    "\n",
    "Optional<std::string> maybe_string_1(\"hello world\");\n",
    "\n",
    "if (maybe_string == \"C++ is designed for faster code\")\n",
    "    std::cout << \"Fast enough?\" << std::endl;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Чтобы не было скучно, добавим в шаблонный класс шаблонный метод.\n",
    "\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class Optional {\n",
    "    ...\n",
    "\n",
    "public:\n",
    "    // уже было\n",
    "    void emplace(const T& another_value) {\n",
    "        value_ = another_value;\n",
    "        has_value_ = true;\n",
    "    }\n",
    "    \n",
    "    // добавили\n",
    "    template<typename U>\n",
    "    void emplace(const U& source) {\n",
    "        value_ = source;\n",
    "        has_value_ = true;\n",
    "    }\n",
    "};\n",
    "\n",
    "//\n",
    "// usage:\n",
    "//\n",
    "Optional<std::string> maybe_string;\n",
    "maybe_string.emplace(\"hello world\");\n",
    "```\n",
    "\n",
    "**Вопрос:** Что поменялось при вызове `emplace`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Самое время добавить в класс шаблонный конструктор!\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class Optional {\n",
    "    ...\n",
    "        \n",
    "public:\n",
    "    // уже было\n",
    "    Optional(const T& another_value)\n",
    "        : value_(another_value)\n",
    "        , has_value_(true)\n",
    "    {}\n",
    "\n",
    "    // добавили\n",
    "    template<typename U>\n",
    "    Optional(const U& source)\n",
    "        : value_(source)\n",
    "        , has_value_(true)\n",
    "    {}\n",
    "};\n",
    "\n",
    "//\n",
    "// usage:\n",
    "//\n",
    "Optional<std::string> maybe_string(\"hello world\");\n",
    "```\n",
    "\n",
    "**Вопрос:** Что поменялось в вызове конструктора от `const char*` ?\n",
    "\n",
    "**Вопрос:** Можем ли мы что-нибудь выиграть от шаблонного деструктора ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример целиком без операторов. Закинуть на godbolt, показать сколько каких методов генерируется, не забыть убрать оптимизации и demangle.\n",
    "\n",
    "```c++\n",
    "#include <string>\n",
    "\n",
    "template<typename T>\n",
    "class Optional {\n",
    "private:\n",
    "    T value_;\n",
    "    bool has_value_;\n",
    "\n",
    "public:\n",
    "    Optional()\n",
    "        : has_value_(false)\n",
    "    {}\n",
    "\n",
    "    Optional(const T& another_value)\n",
    "        : value_(another_value)\n",
    "        , has_value_(true)\n",
    "    {}\n",
    "\n",
    "    template<typename U>\n",
    "    Optional(const U& source)\n",
    "        : value_(source)\n",
    "        , has_value_(true)\n",
    "    {}\n",
    "\n",
    "    Optional(const Optional&) = default;\n",
    "    Optional(Optional&&) = default;\n",
    "    Optional& operator = (const Optional&) = default;\n",
    "    Optional& operator = (Optional&&) = default;\n",
    "    ~Optional() = default;\n",
    "\n",
    "    bool has_value() const { return has_value_; }\n",
    "\n",
    "    T&       get_value()       { return value_; }\n",
    "    const T& get_value() const { return value_; }\n",
    "\n",
    "    T*       get_ptr()       { return has_value_ ? &value_ : nullptr; }    \n",
    "    const T* get_ptr() const { return has_value_ ? &value_ : nullptr; }\n",
    "\n",
    "    void reset() {\n",
    "        value_ = T();\n",
    "        has_value_ = false;\n",
    "    }\n",
    "\n",
    "    void reset(const T& another_value) {\n",
    "        value_ = another_value;\n",
    "        has_value_ = true;\n",
    "    }\n",
    "\n",
    "    void emplace() {\n",
    "        value_ = T();\n",
    "        has_value_ = true;\n",
    "    }\n",
    "\n",
    "    template<typename U>\n",
    "    void emplace(const U& source) {\n",
    "        value_ = T(source);\n",
    "        has_value_ = true;\n",
    "    }\n",
    "};\n",
    "\n",
    "\n",
    "std::string f() {\n",
    "    Optional<std::string> opt;\n",
    "\n",
    "    opt.emplace(\"hello\");\n",
    "    opt.emplace(\"C++\");\n",
    "    opt.emplace(\"world\");        \n",
    "\n",
    "    opt.emplace(std::string(\"-hello\"));\n",
    "    opt.emplace(std::string(\"-C++\"));\n",
    "    opt.emplace(std::string(\"-world\"));\n",
    "\n",
    "    return opt.get_value();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Специфика компиляции шаблонов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создадим свой собственный тип, которому запретим copy assignment:\n",
    "\n",
    "```c++\n",
    "class C {\n",
    "public:\n",
    "    C() = default;\n",
    "    C(const C&) = default;\n",
    "    C(C&&) = default;\n",
    "    C& operator = (const C&) = delete;  // DELETE\n",
    "    C& operator = (C&&) = default;\n",
    "    ~C() = default;\n",
    "};\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сделаем от него `Optional`:\n",
    "\n",
    "```c++\n",
    "Optional<C> opt;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос:** Какие-нибудь возникли подозрения?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ответ: компилируются только те методы, что вызываются:\n",
    "        \n",
    "```c++\n",
    "Optional<C> opt1;       // ok\n",
    "Optional<C> opt2;       // ok\n",
    "Optional<C> opt3(C());  // ok\n",
    "\n",
    "if (opt1 == opt2)  // ok\n",
    "    std::cout << \"equal!\" << std::endl;\n",
    "\n",
    "if (opt1 != opt3)  // ok\n",
    "    std::cout << \"not equal!\" << std::endl;\n",
    "\n",
    "opt1.reset();  // ok\n",
    "\n",
    "opt1 = opt3;       // compilation error: C::operator = (const C&) is deleted\n",
    "\n",
    "opt1.reset(C());   // compilation error: C::operator = (const C&) is deleted\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Member types"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<typename T, unsigned N>\n",
    "class StaticArray\n",
    "{\n",
    "    using value_type = T;\n",
    "\n",
    "    T data_[N];\n",
    "    \n",
    "    const T& operator[](unsigned ix) const { return data_[ix]; }\n",
    "    unsigned size() const { return size_; }\n",
    "    ...\n",
    "};\n",
    "\n",
    "template<typename T>\n",
    "class DynamicArray\n",
    "{\n",
    "    using value_type = T;\n",
    "\n",
    "    T *data_;\n",
    "    unsigned size_;\n",
    "    \n",
    "    const T& operator[](unsigned ix) const { return data[ix]; }\n",
    "    unsigned size() const { return size_; }\n",
    "    ...\n",
    "};\n",
    "\n",
    "\n",
    "//\n",
    "// usage:\n",
    "//\n",
    "template<typename ArrayT>\n",
    "void print_sum(const ArrayT& a) {\n",
    "    typename ArrayT::value_type sum{};\n",
    "    for (unsigned i = 0; i < a.size(); ++i)\n",
    "        sum += a[i];\n",
    "    \n",
    "    std::cout << sum;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### just for fun: compile-time факториал"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь мы разбираемся в шаблонах достаточно чтобы посчитать факториал во время компиляции на шаблонах (разобрать пример, показать результат в godbolt).\n",
    "\n",
    "Примечание: C++ значительно эволюционировал, и больше во время компиляции таким образом вычисления не проводят. Пример исключительно ученический. Compile-time вычисления будут рассмотрены в курсе далее."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<unsigned N>\n",
    "struct Factorial\n",
    "{\n",
    "    static const int value = N * Factorial<N - 1>::value;\n",
    "};\n",
    "\n",
    "template<>\n",
    "struct Factorial<0>\n",
    "{\n",
    "    static const int value = 1;\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    return Factorial<10>::value;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопросы__:\n",
    "* Что делает следующий пример?\n",
    "\n",
    "```c++\n",
    "#include <cstdio>\n",
    "\n",
    "template<unsigned N>\n",
    "struct f\n",
    "{\n",
    "    static const int value = f<N-1>::value + f<N-2>::value;\n",
    "};\n",
    "\n",
    "template<>\n",
    "struct f<0>\n",
    "{\n",
    "    static const int value = 0;\n",
    "};\n",
    "\n",
    "template<>\n",
    "struct f<1>\n",
    "{\n",
    "    static const int value = 1;\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    printf(\"%i\\n\", f<45>::value);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Примеры шаблонных функций / классов из стандартной библиотеки"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотреть примеры подробнее, специализации (если есть). Показать секции member types, non-member functions etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/numeric/complex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "За пределами лекции:\n",
    "* Частичная специализация шаблонов (для классов)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во второй части курса про шаблоны:\n",
    "* SFINAE\n",
    "* variadic templates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечания после лекции:**\n",
    "    \n",
    "* По традиции осталось минут 30 от лекции. Это время можно разбавить примерами или рассказать что-нибудь полезное.\n",
    "* Переделать материал по member types. Сейчас сумбурно и не очевидно, зачем он нужен."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
